/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
 * @author: WXY
 * @create: 2022-12-11 19:46
 * @Version 1.0
 **/


public class Num_offer2_003_countBits {
    public static int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int num = 0; num <= n; num++) {
            ans[num] = oneNumBits(num);
        }
        return ans;
    }

    public static int oneNumBits(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }


    public static int[] countBits1(int n) {
        int[] ans = new int[n + 1];
        int i = 1;
        for (int j = 0; j <= n; j++) {
            if (j % 2 == 0) {
                ans[j] = ans[j / 2];
            } else {
                ans[j] = ans[j / 2] + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] ans = countBits(5);
        for (int num : ans) {
            System.out.println(num);

        }

    }

}
